package L611;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: javase
 * @description: 三数之和
 * @author: luolidong
 * @create: 2021-06-11 14:58
 * @version: 1.0
 */
public class Demo {
    public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> list=new ArrayList<>();
//        排序
        Arrays.sort(nums);
//
        for (int i = 0; i < nums.length ; i++) {
            int s=-nums[i];
//            左右指针
            int l=i+1;
            int r=nums.length-1;
            while (l<r){
//                >0
                if(nums[l]+nums[r]>s){
                    r--;
                }else if(nums[l]+nums[r]<s){
                    l++;
                }else {
                    List<Integer> clist=new ArrayList<>();
                    clist.add(nums[i]);
                    clist.add(nums[l]);
                    clist.add(nums[r]);
                    list.add(clist);
//                    去除相同的元素
                    while (l<r&&nums[l+1]==nums[l]){
                        l++;
                    }
                    while (l<r&&nums[r-1]==nums[r]){
                        r--;
                    }
                    l++;
                    r--;
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = new Demo().threeSum(new int[]{-1, -2, -1, 4, 3});
        System.out.println(lists);
    }
}
